This invention relates generally to channel encoders which generate error correcting codes for data communications over impaired channels. More particularly, the present invention concerns channel encoders which generate rotationally invariant trellis codes when used with a signal constellation comprised of a plurality of subconstellations which are rotations of each other.
The use of channel encoders which supply redundancy to information which is to be transmitted over impaired channels and thereby guarantee accuracy within desired degrees of certainty are known in the art (see, e.g. U.S. Pat. No. 4,562,425 to Turner et al., and Forney Jr., G. David et al., "Efficient Modulation for Band-Limited Channels", IEEE Journal on Selected Areas in Communications, Vol. SAC-2, No. 5 (September 1984 pgs 632-646). A particular class of such encoders are known as "Trellis" encoders. Broadly speaking, trellis encoders take an input which is chosen from a specified alphabet of inputs symbols, and based on the input and the state of the encoder (which is based on the previous history of inputs and states) provides an ouput chosen from an alphabet of output symbols. The distinguishing property of a trellis encoder is that each output symbol indicates in a predetermined way a real vector taken from a specified set of real vectors; the specified set constituting a signal constellation. In transmitting a signal constellation via quadrature amplitude modulation, the signal constellation must comprise a subset of either the Euclidean plane, or a Cartesian product of a fixed number of Euclidean planes. In other words, the signal constellation may be expressed as a union of two-dimensional or 2n-dimensional points. The points in the Euclidean plane then represent quadrature amplitude modulated signals with each point having a particular power associated with it (the squared Euclidean distance to the origin) due to its location in the plane.
Trellis coding supplies relative immunity to noise and other impairments of a transmitting channel by providing a relatively large separation (i.e. Euclidean distance) between the sequences of constellation points generated by the encoder (i.e. encoder outputs). Inherently, this separation takes the form of power differences, the efficacy of which is measured vis-a-vis the average power of the constellation. As a result, it is beneficial for trellis encoders to use constellations in which the ratio of average power divided by the squared Euclidean distance between closest constellation points is relatively low. Such constellations typically possess much circular symmetry.
While circularly symmetric constellations have certain beneficial aspects as described above, those skilled in the art will recognize that if an R-degree rotation about an origin takes a constellation to itself (i.e. circular symmetry), then the combination of channel corruption followed by channel equalization can result in R-degree phase offset, wherein each term in the received sequence is a corrupted version of the R-degree rotation of a corresponding term in the transmitted sequence. One manner of dealing with phase offset is to provide a rotationally invariant encoding scheme (See, e.g. Wei, Lee-Fang, Rotationally Invariant Convolutional Channel Coding with Expanded Signal Space--Part II; Nonlinear Codes, "IEEE Journal on Selected Areas in Communications, Vol SAC-2, No. 5" September 1984 pgs 672-686). In such a scheme, for each rotation taking the constellation to itself, there must be a corresponding transformation of the encoder's set of states and a corresponding transformation of the input alphabet. With rotational invariance, compensation for the phase offset may then be accomplished by precoding the input stream using the technique known as differential encoding.
Trellis codes employing "set-partitioned" constellations are also well known in the art (See, e.g. Ungerboeck, Gottfried, "Channel Coding with Multilevel/Phase Signals", IEEE Transactions on Information Theory, Vol IT-28 No. 1, (January 1982). For such codes, the constellation is divided into non-overlapping, equal-sized subsets, which herein are termed "subconstellations". The essential feature of subconstellations is that the separation between the closest two points within each subconstellation exceeds the separation between the closest two points within the constellation as a whole. With the use of subconstellations, an encoder ouput symbol is preferably generated in two steps. First, a subconstellation is selected. Next, a point in the subconstellation is identified. As such, encoder output symbols may thought of as a pair of labels, with a first term being a subconstellation label, and a second term being a point label.
Depending upon the speed of data transmission, and the amount of redundancy required due to encoding, constellations of different sizes (i.e. amount of points) are required. In choosing the constellation points, it is known that it is beneficial to divide the points into groups of subconstellations which are rotations of other subconstellations. Moreover, it is desirable to provide a constellation which has as much circular symmetry as possible, as the average power of the constellation may be reduced thereby. Thus, many of the constellations of the art, which are based on a square grid, are often seen to have points chosen to provide as circular an arrangement as possible. Other known constellations are based on an hexagonal grid (See, e.g. U.S. Pat. No. 4,538,284 to Lang et al.,) as the hexagonal grid permits a dense and nearly circular constellation.